19.4 余裕ベースリアルタイムコレクション
Henriksson
リアルタイムコレクタのスケジューリング問題にチャレンジ
優先度の高いリアルタイムタスクの実行中はガベージコレクションをまったく行わないという戦略
高優先度タスクが実行可能でなくなってからガベージコレクション処理を行う
高優先度タスクの割り付けにはペナルティなし
低優先度タスクは割り付け時にコレクタ処理も行う
特殊な高優先度GCタスク (high-priority garbage collection task)が高優先度タスクによって省略されたコレクタ処理を受け持つ
高優先度タスクの急な割り付け要求に応えられるように、十分な初期化済み空きメモリを常に余裕を持って確保したまま実行する
図19-4
https://gyazo.com/fee0e796e83c68b637b8127878b85a58
新しいオブジェクトはto空間のトップへ割り付ける
from空間から脱出したオブジェクトはto空間のボトムへコピーする
Cheneyスタイルで走査する cf. 図4-1, p59
低優先度スレッドは新しいオブジェクトの割り付けの際にこのオブジェクト脱出処理をインクリメンタルに手伝う
scanポインタで脱出済みオブジェクト走査の進捗を表示
すべてのアクセスで間接バリアを用いるBrooksスタイルの並行コピーGCに、書き込みの新しいターゲットオブジェクトがto空間にあることの保証を加えたもの
オブジェクトに転送先をもたせてRead時には常に転送先から読む
並行GCの強い不変条件を保つ
to空間オブジェクトがfrom空間への参照を持たない
15.1 強い三色不変条件（the strong tricolour invariant）
黒いオブジェクト(=to空間のオブジェクト)から白いオブジェクト(=from空間のオブジェクト)を指すポインタが存在しない。
高優先度タスクのライトバリアは単にto空間に複製用の空間を割り付けるだけ
from空間のオリジナルの内容の転送を遅延
GCがその空間を走査する必要に迫られたときに延期されたコピーを実施する
高優先度GCタスクの仕事または低優先度タスクの税金として
to空間のコピーのヘッダにはfrom空間のオリジナルを指すバックポインタをもたせる(図19-5)
https://gyazo.com/7d8faa6a8cce2bdbd3c5519daa919f23
Brooksの間接バリアを用いて、空のto空間コピーへアクセスされる前にfrom空間からコピーできるように
Bakerと違って、ミューテータではなくコレクタがto空間不変条件を守る
ミューテータのリードバリアはオブジェクトを転送しない
Brooksの間接バリアのおかげでちゃんとアクセスはできる
不変条件を守るためのコピーは遅延されてコレクタが実行する
ミューテータのライトバリアで発生したコピー要求を遅延させ、(Sapphire(17.6 Sapphire)のように)コレクタがあとから実行する 一時的に使われるtoAddressフィールドのポインタを利用することで、コレクタはto空間の複製が持つ参照from空間のオブジェクトを、ミューテータがfrom空間で動作を続けている間であっても転送することができる。
わかりにくいので翻訳する
forwardingAddressとは別の(ヘッダ上の)フィールドとして、toAddressフィールドが必要ということ
BrooksのReadバリアでは常にforwardingAddress経由でフィールドを読む
forwardingAddressは常に有効な領域を指し続けないといけないので、オブジェクトの転送先が決まった段階では、そのto空間の領域は空なので、まだforwardingAddressはfrom空間のオリジナルを指している必要がある
しかし、転送先も記憶しておく必要があるので、そのためにtoAddressフィールドがある
toAddressの情報がforwardingAddressとは別になっているので、当然転送は問題なくできる
コレクタはコルーチンになっている
決まったタイミング(yield)で低優先度ミューテータタスクと交代する
高優先度タスクはいつでも割り込める
コレクタがコピー中ならその作業はアボートして制御が戻ったときにやり直す
アボートは強制終了。本当に任意のタイミングで呼び出し元から止めることができる。
どのようにアボートしたりやり直したりするのかは明示されてない
ユニプロセッサのプラットフォームと仮定
不可分操作をスケジューラの割り込み禁止によって実装できる
code:アルゴリズム19-5.py
coroutine collector:
loop:
while bottom < top: # to空間がいっぱいでない
yield # ミューテータに戻る
flip()
for fld in Roots:
process(fld)
# behind() == falseでは処理すべき仕事がもうない
if not behind():
yield
while scan < bottom:
scan = scanObject(scan)
if not behind():
yield
def flip():
toBot, fromBot = fromBot, toBot
toTop, fromTop = fromTop, toTop
bottom, top = toBot, toTop
scan = bottom
def scanObject(toRef):
fromRef = forwardingAddress(toRef)
move(fromRef, toRef) # shallow copy
for fld in Pointers(toRef):
process(fld)
forwardingAddress(fromRef) = toRef
forwardingAddress(toRef) = toRef # こっちもやるべきでは？
return toRef + size(toRef)
def process(fld):
fromRef = *fld
if fromRef != null:
*fld = forward(fromRef) # to空間への参照に更新
def forward(fromRef):
toRef = forwardingAddress(fromRef)
if toRef == fromRef: # 未脱出
toRef = toAddress(fromRef)
if toRef == null: # 脱出スケジュールは未定(未マーク)
toRef = schedule(fromRef)
return toRef
def schedule(fromRef): # to空間の複製のための空き領域を作成
toRef = bottom
bottom = bottom + size(fromRef)
if bottom > top:
error "Out of memory"
toAddress(fromRef) = toRef # 脱出をスケジュール(マーク)する
forwardingAddress(toRef) = fromRef # この初期化が必要では？
return toRef
code:アルゴリズム19-6.py
atomic Read(src, i):
src = forwardingAddress(src) # Brooksの間接操作
atomic Write(src, i, ref):
src = forwardingAddress(src) # Brooksの間接操作
if ref in fromspace:
ref = forward(ref)
atomic NewHighPriority(size):
top = top - size
toRef = top
forwardingAddress(toRef) = toRef
return toRef
atomic NewLP(size):
while behind():
yield # コレクタを起こす
top = top - size
toRef = top
if bottom > top:
error "Out of memory"
forwardingAddress(toRef) = toRef
return toRef
コレクタ処理のスケジューリング
1つのタイムスライスでの作業量
behindの呼び出しで制御
to空間がいっぱいになる前にfrom空間からの脱出処理とコレクタサイクルの終了を保証できる余裕が必要
GCサイクルを完了するために必要な作業量の最大値$ W_{max}
以下を行うためのメモリを初期化するのに必要な作業量(処理するバイト数)
from空間から生きているオブジェクトをすべて脱出させる
GCサイクル中の高優先度スレッドの割り付け要求
GCサイクルが完了した時点の空き領域の最小値$ F_{min}
最小GC率$ GCR_{min}
$ GCR_{min}=\frac{W_{max}}{F_{min}}
現在のGC率$ GCR
$ GCR = \frac{W}{A}
実施されたGC処理$ W
GC作業により増える
to空間に新たに割り付けられたオブジェクトの量$ A
ミューテータの割り付けにより増える
コレクタは$ Wを増やして($ GCR\ge GCR_{min})を保つ必要がある(=目安に頑張る程度の意味)
最悪ケースでもto空間がいっぱいになる前にfrom空間が空になる
コレクタのタスクに高い優先度を与えて低優先度タスクの割り付けを抑制する
割り付けによって$ Aが増えると$ GCRが下がる
割り付けられるオブジェクトサイズに比例して、その期間中のコレクタの作業量の上界が定まる
高優先度タスクがflipの直前にアクティブになったときを考える
高優先度タスクの割り付けとfrom空間からの最後の脱出との両方ができるだけの余裕がto空間に必要
高優先度タスクが現在のサイクル中に割り付けるオブジェクトが収まるサイズ
アプリケーション開発者に求められる見積もり
高優先度タスクの動作に必要な最悪ケースの割り付け量
割り付け間隔
各間隔の最悪ケース実行時間
Henriksson曰く見積もりは容易
高優先度タスクは高速・小規模でメモリ割り付けはほとんどしない
各タスクのデッドライン、タスクの間隔を入力として、必要なメモリの余裕とスケジュール可能性を出力する解析的フレームワークを提供
実行オーバーヘッド
高優先度タスクに対するコレクタの活動のオーバーヘッド
メモリ割り付け・ポインタ間接参照・ポインタ書き込みに要する命令数の上界から求める
キャッシュミスがあり得るので時間の尺度にはならない
最悪実行時間解析ではキャッシュを無効化するかシステムの実証テストが必要
それぞれのオーバーヘッドの最悪ケース
ヒープアクセス
転送ポインタの間接参照(1命令)
forwardingAddressをたどる処理
割り込みを禁止するオーバーヘッド(バリア)
ポインタ書き込み
ターゲットを後で脱出させるようにマーク(20命令)
refがfrom空間の参照の場合にforward(ref)内部でto空間の複製のための領域割り当てが発生
割り込み割り付けの間違い？
ポインタをずらしてヘッダに転送ポインタ等を書き込んで初期化(10命令)
NewHighPriority(size)
遅延時間の最悪ケース
コレクタが実行中の不可分処理を完了またはアボートするまでの時間に依存
短くて有界
Henriksson曰くコンテキストスイッチコストのほうが支配的
低優先度タスクのオーバーヘッド
ヒープアクセスやポインタ書き込みは高優先度タスクと同じ
割り込みの最悪ケース
新しく割り付けるオブジェクトサイズに比例
behind()の呼び出し結果による
厳密には以下に依存
最大オブジェクトサイズ
ヒープサイズの合計
生きているオブジェクト集合の最大値
1回のGCサイクル中にコレクタが行う作業量の最大値
プログラマの入力
コレクタが高優先度タスク群の邪魔をしないようにするためには、アプリケーションプログラムと高優先度タスク群に関する情報提供が必要
最小GC率を計算し、プログラム実行中に現在のGC率を追跡するために必要
高優先度の割り付け要求を常に満たせる最低限のバッファ量の計算に必要な情報：
高優先度タスクすべてについての
実行間隔
最悪ケース実行時間
周期的な起動1回に最悪ケースで必要となる割り付け量
高優先度リアルタイムタスク群に対する最悪実行時間解析とスケジュール可能性解析のためには、上に加えて最大の生きているメモリフットプリントの推定値も必要